package chapter5.section5

/**
 * 设Fk是第k个斐波那契数。假设有一个符号序列，其中第k个符号的频率为Fk。
 * 注意，F1+F2+...+FN=F(N+2)-1。给出相应的霍夫曼编码。
 * 提示：最长的编码的长度为N-1。
 *
 * 解：斐波那契数列为0、1、1、2、3、5、8、13、21...，后一个值等于前两个值之和，
 * 由题可知，斐波那契数列单调递增，且前N个元素（N>=2）的和大于等于第N+1个元素，小于第N+2个元素，
 * 霍夫曼编码在构造树时，频率较小的结点在左侧，较大的结点在右侧，相等的结点位置任意，
 * 对于数列中的第k个元素来说，k==1的元素不在霍夫曼树中，
 * k==2和k==3的元素组成路径最长的两个叶子结点，构造成一颗树，左右顺序任意（因为频率相等，从小顶堆中弹出的顺序不确定）
 * k==4的元素和 前两个元素组成的树 组成一个新的树，左右顺序任意，
 * k>=5的元素和前面组成的树组成一个新树，第k个元素必定在左分支（因为前N个元素的和大于第N+1个元素，小于第N+2个元素）
 * 以前6个元素为例，斐波那契数列构成的树可能是以下四种之一：
 * （6:5表示第6个元素的频率为5，_:12表示非叶子结点的结点频率为12）
 *     _:12                    _:12                    _:12                   _:12
 *    /   \                   /   \                   /   \                  /   \
 *  6:5   _:7               6:5   _:7               6:5   _:7              6:5   _:7
 *       /   \                   /   \                   /   \                  /   \
 *      5:3  _:4                5:3  _:4                5:3  _:4               5:3  _:4
 *          /   \                   /   \                   /   \                  /   \
 *         4:2  _:2                4:2  _:2                _:2   4:2              _:2  4:2
 *             /   \                   /   \              /   \                  /   \
 *            3:1  2:1                2:1  3:1           3:1  2:1               2:1  3:1
 * 具体是哪种结构和最小优先队列在处理相等元素时的实现及插入顺序有关
 * 所以，若斐波那契数列的总数为N，
 * 当k>=5时，第k个元素的霍夫曼编码以N-k个1开头，以0结尾，
 * 当k==4时，第k个元素的霍夫曼编码以N-4个1开头以0结尾，或者，包含N-3个1
 * 当k==3或k==2时，第k个元素的霍夫曼编码以N-4个1开头，以10或11或01或00结尾
 * 以N=6为例，k==6的编码为0，k==5的编码为10，k==4的编码为110或111
 * k==3和k==2的编码为1110或1111或1100或1101
 */
fun main() {
    val huffman = Huffman()
    val dump = BinaryDump(8, 8)

    val s1 = "bcddeeefffff"
    println("s1: $s1")
    // 霍夫曼编码树和注释中的第二个结构相同
    compressAndDumpString(s1, huffman, dump)

    val s2 = "feddcccbbbbb"
    println("s2: $s2")
    // 霍夫曼编码树和注释中的第一个结构相同
    compressAndDumpString(s2, huffman, dump)
}